# Definition for a binary tree node.
class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right
class Solution:
    def generateTrees(self, n: int):
        if n == 0:
            return []
        return self.generateTrees2(1, n, {})

    def generateTrees2(self, start, end, cahce):
        if (start,end) in cahce:
            return cahce[(start,end)]
        if start>end:
            return [None]
        allTree = []
        for i in range(start, end+1):
            leftList = self.generateTrees2(start, i-1, cahce)
            rightList = self.generateTrees2(i+1,end, cahce)
            for left in leftList:
                for right in rightList:
                    allTree.append(TreeNode(i,left, right))
        cahce[(start, end)] = allTree
        return allTree


if __name__ == '__main__':
    so = Solution()
    n = 3
    r = so.numTrees(n)
    print(r)
